package main

import "fmt"

/*
最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：
输入：s = ""
输出：0
*/
func longestValidParentheses(s string) int {
	//var stack1 []byte //记录括号的栈
	var stack2 []int //记录括号下标的栈
	mark := make([]int, len(s), len(s))
	for i := 0; i < len(s); i++ {
		mark[i] = 0
	}
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			//stack1 = append(stack1, s[i]) //左括号 下标入栈
			stack2 = append(stack2, i)
		} else if len(stack2) != 0 && s[stack2[len(stack2)-1]] == '(' { //右括号 且栈顶元素(下标)在s中为左括号的话 出栈
			//stack1 = stack1[:len(stack1)-1]
			stack2 = stack2[:len(stack2)-1]
		} else { //匹配不上的右括号 标记
			mark[i] = 1
		}
	}
	for _, v := range stack2 {
		if s[v] == '(' { //匹配不上的左括号 标记 k为栈2的下标 用于看对应下标的栈1中是否为左括号
			mark[v] = 1
		}
	}
	//寻找最长的0的长度
	cur, res := 0, 0
	for i := 0; i < len(mark); i++ {
		if mark[i] == 1 {
			cur = 0
		} else {
			cur++
			res = max(cur, res)
		}
	}
	return res
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func main() {
	s := ")()((())"
	fmt.Println(longestValidParentheses(s))
}
